package com.cet.qz.unit01.chapter1_3;

/**
 * @program: algorithm
 * @description: 双向链表
 * @author: 陈恩涛
 * @create: 2021-04-19 09:41
 **/
public class MyDoubleLinkedList<Item> {

    private DoubleNode first;
    private int n;

    private class DoubleNode {
        private Item item;
        private DoubleNode prior;
        private DoubleNode next;
    }

    public boolean isEmpty() {
        return first == null;
    }

    /**
     *方法描述： 表头插入节点
     *
     * @param item
     * @return void
     * @author chenentao
     * @date 2021/4/19 10:22
     */
    private void addHeadNode(Item item) {
       DoubleNode head = new DoubleNode();
        head.item = item;
        if (isEmpty()) {
            first = head;
        } else {
            first.prior = head;
            head.next = first;
            first = head;
        }
        n++;
    }

    /**
     *方法描述： 表尾插入节点
     *
     * @param item
     * @return void
     * @author chenentao
     * @date 2021/4/19 10:22
     */
    private void addTailNode(Item item) {
        DoubleNode tail = new DoubleNode();
        tail.item = item;
        if (isEmpty()) {
            first = tail;
        } else {
            DoubleNode temp = first;
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = tail;
            tail.prior = temp;
        }
        n++;
    }

    /**
     *方法描述： 删除表头节点
     *
     * @param
     * @return void
     * @author chenentao
     * @date 2021/4/19 10:21
     */
    private void delHeadNode() {
        if (isEmpty()) {
            throw new RuntimeException("双向链表为空！");
        }
        if (n == 1) {
            first = null;
        } else {
            first.next.prior = null;
            first = first.next;
        }
        n--;
    }

   /**
    *方法描述： 删除表尾节点
    *
    * @param
    * @return void
    * @author chenentao
    * @date 2021/4/19 10:21
    */
    private void delTailNode() {
        if (isEmpty()) {
            throw new RuntimeException("双向链表为空！");
        }
        if (n == 1) {
            first = null;
        } else {
            DoubleNode temp = first;
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.prior.next = null;
            temp.prior = null;
        }
        n--;
    }

    /**
     *方法描述： 删除第k个节点
     *
     * @param k
     * @return void
     * @author chenentao
     * @date 2021/4/19 10:27
     */
    private void delete(int k) {
        if (k > n) {
            throw new RuntimeException("Index is out of bounds!");
        }
        if (k <= 0) {
            throw new RuntimeException("paramater required a Positive integer");
        }
        if (k == 1) {
            delHeadNode();
        } else {
            DoubleNode temp = first;
            while (k > 2) {
                temp = temp.next;
                k--;
            }
            temp.next.prior = null;
            temp.next = temp.next.next;
            if (temp.next != null) {
                temp.next.prior.next = null;
                temp.next.prior = null;
            }
            n--;
        }
    }

    /**
     *方法描述： 在第k个节点前插入节点
     *
     * @param k
     * @param item
     * @return void
     * @author chenentao
     * @date 2021/4/19 11:08
     */
    private void addPriorNode(int k, Item item) {
        if (k > n) {
            throw new RuntimeException("Index is out of bounds!");
        }
        if (k <= 0) {
            throw new RuntimeException("paramater required a Positive integer");
        }
        if (k == 1) {
            addHeadNode(item);
        } else {
            DoubleNode target = first;
            while (k > 1) {
                target = target.next;
                k--;
            }
            DoubleNode insert = new DoubleNode();
            insert.item = item;
            target.prior.next = insert;
            insert.prior = target.prior;
            target.prior = insert;
            insert.next = target;
            n++;
        }
    }

    /**
     *方法描述： 在第k个节点后插入节点
     *
     * @param k
     * @param item
     * @return void
     * @author chenentao
     * @date 2021/4/19 10:25
     */
    private void addNextNode(int k, Item item) {
        if (k > n) {
            throw new RuntimeException("Index is out of bounds!");
        }
        if (k <= 0) {
            throw new RuntimeException("paramater required a Positive integer");
        }
        if (k == n) {
            addTailNode(item);
        } else {
            DoubleNode target = first;
            while (k > 1) {
                target = target.next;
                k--;
            }
            DoubleNode insert = new DoubleNode();
            insert.item = item;
            target.next.prior = insert;
            insert.next = target.next;
            target.next = insert;
            insert.prior = target;
            n++;
        }
    }


    @Override
    public String toString() {
        StringBuilder str = new StringBuilder();
        for (DoubleNode x = first; x != null; x = x.next) {
            str.append(x.item);
            str.append(" ");
        }
        return str.toString();
    }

    public static void main(String[] args) {
        MyDoubleLinkedList<Integer> doubleLinkedList = new MyDoubleLinkedList<>();
        doubleLinkedList.addHeadNode(1);
        doubleLinkedList.addHeadNode(2);
        doubleLinkedList.addTailNode(3);
        doubleLinkedList.addTailNode(4);
        doubleLinkedList.addTailNode(5);
        doubleLinkedList.delHeadNode();
        doubleLinkedList.delTailNode();
        doubleLinkedList.delete(1);
        doubleLinkedList.delete(2);
        doubleLinkedList.addPriorNode(1,6);
        doubleLinkedList.addPriorNode(2,7);
        doubleLinkedList.addNextNode(3,8);
        doubleLinkedList.addNextNode(2,9);
        System.out.println(doubleLinkedList);
    }


}
